<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            分割等和子集：
            输入：nums = [1,5,11,5]
            输出：true
            解释：数组可以分割成 [1, 5, 5] 和 [11]

            判断是01背包：
            1. 每个数字只能取1次，是01背包；取很多次就是完全背包 ==> 背包中每个元素是“不重复”放进去的
            2. 背包体积为 sum/2，因为两个子集的数字和相等
            3. 背包里面要放入的商品，重量为元素的数值，价值也为元素的数值 ==> 很神奇，这两个竟然一样
            4. 背包装满，表示找到了元素的子集


            五部曲：
            1. dp[j]的含义：j是背包的容量，dp[j]是拿到数字的最大和，最大重量和也是最大价值和
            => 如果背包容量是target,dp[target] === target,背包装满
            => dp[7] = 6，因为7是容量，但是只能放1和5,是6，再放就是1 5 5 或者 1 5 11就超过了
            2. 确定递推公式：dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]) 注意，nums[i]不仅是重量，也是价值
            3. 初始化dp数组，如果遍历的数字都是正整数，可以都初始化为0，否则要初始化负无穷？为什么
            4. 确定遍历顺序，和01背包一样，先遍历数字，再遍历背包的容量；遍历背包的容量时要倒序遍历
            5. 递推一下：重点 dp[j] <= j，如果等于，说明背包正好装满了

        */
        var lastStoneWeightII = function (stones) {
            let sum = stones.reduce((s, n) => s + n);
            let dpLen = Math.floor(sum / 2);
            let dp = new Array(dpLen + 1).fill(0);
            for (let i = 0; i < stones.length; ++i) {
                for (let j = dpLen; j >= stones[i]; --j) {
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
            return dp[dpLen] === sum
        };
        console.log(lastStoneWeightII([31,26,33,21,40]));
    </script>
</body>

</html>